class Solution {
public:

    int MoreThanHalfNum_Solution(vector<int>& numbers)
    {
        // write code here
        sort(numbers.begin(), numbers.end());

        int dest = 0;
        int cur = 0;
        int count = 0;

        for (int i = 0; i < numbers.size(); i++)
        {
            if (numbers[dest] == numbers[cur])
            {
                cur++;
                count++;
            }
            else
            {
                if (count > numbers.size() / 2)
                {
                    return numbers[dest];
                }
                else
                {
                    count = 0;
                    dest = cur;
                }
            }
        }

        return numbers[dest];
    }
};
